#
# @lc app=leetcode.cn id=84 lang=python3
#
# [84] 柱状图中最大的矩形
#

# @lc code=start

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 单调栈
        stack = [0] # 初始化为-1
        heights += [0] #?
        s = 0
        for i in range(len(heights)):
            while stack and heights[i] <= stack[0]: # 当前元素<栈顶元素,入栈
                stack.pop()
                i+=1
            stack.append(heights[i])
            # left, right = heights.index(stack[-1]), heights.index(heights[i])
            print(f"stack={stack}")
            left, right = heights.index(height), i
            print(f'height={height} left={left} right={right}')
            width = right - left -1
            s = max(s, width*height)
            print(f's={s} {width*height}')
        return s
# @lc code=end

